import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-11-28
 * Time: 13:21
 */
public class slousion5 {
    //堆排序
    public static void swap(String[] arr,int a, int b){
        String tmp=arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }
    public static void sort(String[] arr){
        int size = arr.length;
        int j=1;
        // 首先构建最大堆
        for (int i = (size - 2) / 2; i >= 0; i--) {
            shiftDown(arr, i, size - 1);
        }
        // 进行堆排序
        while (size > 1) {
            swap(arr, 0, size - 1); // 将最大值移到数组末尾
            size--; // 缩小堆的范围
            shiftDown(arr, 0, size - 1); // 重新调整堆
            System.out.println("第"+j+++"次: "+ Arrays.toString(arr));
        }
    }

    public static void shiftDown(String[] arr, int parents,int pos) {
        int largest = parents; // 记录最大值的下标
        int leftChild = 2 * parents + 1;
        int rightChild = 2 * parents + 2;

        // 比较父节点和左子节点
        if (leftChild <= pos && arr[leftChild].compareTo(arr[largest])>0) {
            largest = leftChild;
        }
        // 比较当前最大值和右子节点
        if (rightChild <= pos && arr[rightChild].compareTo(arr[largest])>0) {
            largest = rightChild;
        }

        // 如果最大值不是父节点，进行交换并递归调整
        if (largest != parents) {
            swap(arr, parents, largest);
            shiftDown(arr, largest, pos);
        }
    }

    public static void main(String[] args) {
        String[] arr=new String[]{"数据结构与算法","计算机导论","离散数学","数字逻辑与计算机组成","程序设计与问题求解","概率论"};
        sort(arr);
    }
}
